//==============================================================================
//
//      DHashTable - the hash table collection class in the ofc-library
//
//               Copyright (C) 2003  Dick van Oudheusden
//  
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this library; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2005-02-05 06:25:38 $ $Revision: 1.11 $
//
//==============================================================================

#include "ofc/DHashTable.h"

#include "ofc/DData.h"


#if _INTERFACE_

#include "ofc/config.h"

#include "ofc/DDatable.h"
#include "ofc/DComparable.h"

#include "ofc/DList.h"

// The hash node is an element in a hash table

typedef struct _DHashNode
{
  id                    _key;
  id                    _object;
  struct _DHashNode    *_next;
  struct _DHashNode    *_prev;
  unsigned long         _hash;
} DHashNode;

// The hash table collection class implements a number of methods for creating, inserting
// searching and removing objects in a hash table.

@interface DHashTable : Object
{
@private
  DHashNode       **_table;    // the actual table with the nodes
  Class             _class;    // the class of the key
  unsigned long     _size;     // the size of the table
  long              _count;    // the number of nodes in the hash table
  double            _load;     // the load factor before resising >0.0
  unsigned long     _threshold;// the threshold for resizing
}

#endif



@implementation DHashTable


#if _PRIVATE_

static DHashNode *newNode(DHashTable *table)
{
  DHashNode *node = (DHashNode *) objc_malloc(sizeof(DHashNode));
  
  node->_key    = nil;
  node->_object = nil;
  node->_next   = NULL;
  node->_prev   = NULL;
  node->_hash   = 0;
  
  (table->_count)++;
  
  return node;
}

static void shallowFreeNode(DHashTable *table, DHashNode *node)
{
  if (node->_key != nil)
    [node->_key free];
    
  node->_next   = NULL;
  node->_prev   = NULL;
  node->_key    = nil;
  node->_object = nil;

  (table->_count)--;

  objc_free(node);
}

static void freeNode(DHashTable *table, DHashNode *node)
{
  if (node->_object != nil)
    [node->_object free];

  shallowFreeNode(table, node);
}

static DHashNode *getNode(DHashTable *table, unsigned long index)
{
  if ((index >= 0) && (index < table->_size))
    return table->_table[index];
  else
    return NULL;
}

#endif


//// Constructors

//
// Initialise an empty hash table with a default size and load
//
// @param key      the class of the key (conforms DDatable and DComparable)
//
// @return the object
//

- (DHashTable *) init :(Class) key
{
  [self init :key :101 :0.75];
  
  return self;
}

//
// Initialise an empty hash table with an initial size
//
// @param key       the class of the key (conforms DDatable and DComparable)
// @param size      the initial size of the table
// @param load      the load factor for resizing
//
// @return the object
//

- (DHashTable *) init :(Class) key :(unsigned long) size :(double) load
{
  [super init];

  if (key == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "key");
  }
  else if (![key isClass])
  {
    WARNING(DW_ARG_NOT_CLASS, "key");
  }
  else if ((![key conformsTo :@protocol(DDatable)]) ||
           (![key conformsTo :@protocol(DComparable)]))
  {
    WARNING(DW_INVALID_PROT, "key");
  }

  _class     = key;
  _table     = NULL;
  _count     = 0;
  _size      = 0;
  _threshold = 0;
  _load      = 1.0;

  [self size :size];
  [self load :load];

  return self;
}


//// Copy related methods

//
// Deepen a copy of the object (not implemented)
//
// @return the object
//

- deepen
{
  [super deepen];

  WARNING(DW_METHOD_NOT_IMPL, "deepen");

  return self;
}


//// Destructor

//
// Free the hash table (the objects are *NOT* freed)
//
// @return the object
//

- shallowFree
{
  unsigned long  index;
  DHashNode     *walk;
  DHashNode     *last;

  for (index = 0; index < _size; index++)
  {
    walk = _table[index];

    while (walk != NULL)
    {
      last = walk->_next;

      shallowFreeNode(self, walk);

      walk = last;
    }
  }
  objc_free(_table);

  [super free];

  return self;
}

//
// (Deep) free the hash table (the stored objects are *FREED*)
//
// @return the object
//

- free
{
  unsigned long  index;
  DHashNode     *walk;
  DHashNode     *last;

  for (index = 0; index < _size; index++)
  {
    walk = _table[index];

    while (walk != NULL)
    {
      last = walk->_next;

      freeNode(self, walk);

      walk = last;
    }
  }
  objc_free(_table);

  [super free];

  return self;
}


//// Member methods

//
// Return the number of elements
//
// @return the length
//

- (long) length
{
  return _count;
}

//
// Check if the hash table is empty
//
// @return is it?
//

- (BOOL) isEmpty
{
  return (_count == 0);
}

//
// Return the load factor
//
// @return the factor
//

- (double) load
{
  return _load;
}

//
// Set the load factor
//
// @param load     the new load factor (> 0.0)
//
// @return the object
//

- (DHashTable *) load :(double) load
{
  if (load > 0.0)
  {
    _load      = load;
    _threshold = (unsigned long) (_size * _load);
  }
  else
    WARNING(DW_INVALID_ARG, "load");

  return self;
}

//
// Return the size of the hash table
//
// @return the size
//

- (unsigned long) size
{
  return _size;
}

//
// Set the size of the hash table
//
// @param size     the new size for the table
//
// @return the object
//

- (DHashTable *) size :(unsigned long) size
{
  if (size > _size)
  {
    if (_count == 0)
    {
      unsigned long index;
      
      _size = size;
      
      if (_table == NULL)
      {
        _table = (DHashNode **) objc_malloc(sizeof(DHashNode *) * _size);
      }
      else
      {
        _table = (DHashNode **) objc_malloc(sizeof(DHashNode *) * _size);
      }

      for (index = 0; index <_size; index++)
      {
        _table[index] = NULL;
      }
    }
    else // rehash
    {
      DHashNode **temp = (DHashNode **) objc_malloc(sizeof(DHashNode *) * size);
      DHashNode  *walk;
      DHashNode  *next;

      unsigned long index;
      unsigned long jndex;

// printf("Resizing: %ld -> %ld for %ld\n", _size, size, _count);

      for (index = 0; index < size; index++)
        temp[index] = NULL;

      for (jndex = 0; jndex < _size; jndex++)
      {
        walk = _table[jndex];
        while (walk != NULL)
        {
          index = (walk->_hash % size);

          next = walk->_next;

          walk->_next  = temp[index];
          walk->_prev  = NULL;
    
          if (temp[index] != NULL) 
            temp[index]->_prev = walk;

          temp[index] = walk;
             
          walk = next;
        }
      }

      objc_free(_table);
      _table     = temp;
      _size      = size;
      _threshold = (unsigned long) (_size * _load);
    }
  }

  return self;
}


//// Hash table manipulation

//
// Insert a key,object in the hash table
//
// @param key      the key to be inserted
// @param object   the object to be inserted
//
// @return success
//

- (BOOL) insert :(id) key :(id) object
{
  unsigned long  hash  = 0;
  unsigned long  index = 0;

  if (key == nil)
  {
    return NO;
  }

  if (![key isKindOf :_class])
  {
    WARNING(DW_INVALID_CLASS, "key");

    return NO;
  }

  {
    DData *data = [key toData];
    hash = [data hash];
    [data free];

    index = hash % _size;
  }

  {
    DHashNode *node = newNode(self);

    node->_hash   = hash;
    node->_key    = [key copy];
    node->_object = object;

    node->_next  = _table[index];
    node->_prev  = NULL;
    
    if (_table[index] != NULL) 
      _table[index]->_prev = node;

    _table[index] = node;
  }

  if (_count > _threshold)
  {
    [self size :(_size * 2 + 1)];
  }

  return YES;
}

//
// Remove a key,object from the hash table
//
// @param key      the key to be removed
//
// @return the object (or nil for not found)
//

- (id) delete :(id) key
{
  DHashNode     *walk   = NULL;
  unsigned long  hash   = 0;
  id             object = nil;
  
  if (key == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "key");
    
    return nil;
  }

  if (![key isKindOf :_class])
  {
    WARNING(DW_INVALID_CLASS, "key");
    
    return nil;
  }

  {
    DData *data = [key toData];
    hash = [data hash];
    [data free];
  }

  walk = _table[hash % _size];
  while (walk != NULL)
  {
    if ((hash == walk->_hash) && ([key compare :walk->_key] == 0))
    {
      break;
    }
    walk = walk->_next;
  }

  if (walk != NULL)
  {
    if (_table[hash % _size] == walk)
      _table[hash % _size] = walk->_next;
    if (walk->_next != NULL)
      walk->_next->_prev = walk->_prev;
    if (walk->_prev != NULL)
      walk->_prev->_next = walk->_next;
 
    object = walk->_object;
    
    shallowFreeNode(self, walk);
  }

  return object;
}

//
// Check if the hash table has a certain key
//
// @param key      the key to be checked
//
// @return is the key present
//

- (BOOL) has :(id) key
{
  DHashNode     *walk = NULL;
  unsigned long  hash = 0;

  if (key == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "key");
    
    return NO;
  }

  if (![key isKindOf :_class])
  {
    WARNING(DW_INVALID_CLASS, "key");

    return NO;
  }

  {
    DData *data = [key toData];
    hash = [data hash];
    [data free];
  }

  walk = _table[hash % _size];
  while (walk != NULL)
  {
    if ((hash == walk->_hash) && ([key compare :walk->_key] == 0))
    {
      break;
    }
    walk = walk->_next;
  }

  return (walk != NULL);
}

//
// Return the object related to the key in the hash table
//
// @param key      the key to be checked
//
// @return the object related to the key (or nil)
//

- (id) get :(id) key
{
  DHashNode     *walk = NULL;
  unsigned long  hash = 0;

  if (key == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "key");
    
    return NO;
  }

  if (![key isKindOf :_class])
  {
    WARNING(DW_INVALID_CLASS, "key");

    return NO;
  }

  {
    DData *data = [key toData];
    hash = [data hash];
    [data free];
  }

  walk = _table[hash % _size];
  while (walk != NULL)
  {
    if ((hash == walk->_hash) && ([key compare :walk->_key] == 0))
    {
      break;
    }
    walk = walk->_next;
  }

  return (walk != NULL) ? walk->_object : nil;
}

//
// Perform a method for every object in the hash table
//
// @param sel      the selector of the method
//
// @return the object
//

- (DHashTable *) each :(SEL) sel
{
  unsigned long  index;
  DHashNode     *walk;

  for (index = 0; index < _size; index++)
  {
    walk = _table[index];

    while (walk != NULL)
    {
      if (walk->_object != nil)
      {
        [walk->_object perform :sel];
      }
      
      walk = walk->_next;
    }
  }

  return self;
}


//// List related functions

//
// Return a list with copies of all keys in the hash table
//
// @return a (new) list with all the keys
//

- (DList *) keys
{
  DList     *list = [[DList alloc] init];
  DHashNode *walk = NULL;

  unsigned long index;

  for (index = 0; index < _size; index++)
  {
    walk = _table[index];

    while (walk != NULL)
    {
      [list append :[walk->_key copy]];

      walk = walk->_next;
    }
  }
  return list;
}

//
// Return a list with copies of all the objects in the hash table
//
// @return a (new) list with all the objects
//

- (DList *) objects
{
  DList     *list = [[DList alloc] init];
  DHashNode *walk = NULL;

  unsigned long index;

  for (index = 0; index < _size; index++)
  {
    walk = _table[index];
  
    while (walk != NULL)
    {
      [list append :[walk->_object copy]];
   
      walk = walk->_next;
    }
  }
  return list;
}

@end



#if _INTERFACE_

// The DHashIterator class implements a number of methods for iterating hash tables.

@interface DHashIterator : Object
{
@private
  DHashTable     *_table;   // the table on which the iterator operates
  DHashNode      *_node;    // the current node in the list
  unsigned long   _index;   // the current index in the hash table
}

#endif



@implementation DHashIterator


//// the constructors

//
// Initialise a hash iterator without a table
//
// @return the iterator
//

- (DHashIterator *) init
{
  [super init];
  
  _table  = nil;
  _node   = NULL;
  _index  = 0;
  
  return self;
}

//
// Initialises an iterator on a hash table (the iterator is moved to the first node)
//
// @param table    the hash table on which the iterator operates
//
// @return the iterator
//

- (DHashIterator *) init :(DHashTable *) table
{
  [self init];

  [self hashTable :table];

  return self;
}


//// the iterator methods

//
// Set the table (iterator is moved to the first object)
//
// @return the object
//

- (DHashIterator *) hashTable :(DHashTable *) table
{
  _table = table;

  [self first];
  
  return self;
}

//
// Get the first object in the table
//
// @return the first object (or nil)
//

- (id) first
{
  _node = NULL;

  if (_table != nil)
  {
    int size = [_table size];

    _index = 0;
    while ((_index < size) && (_node == NULL))
    {
      _node = getNode(_table, _index);

      _index++;
    }
    _index--;
  }
  else
    WARNING(DW_OBJECT_NOT_INIT, "hashTable");
    
  return (_node != NULL) ? _node->_object : nil;
}

//
// Get the next object in the table
//
// @return the next object (or nil)
//

- (id) next
{
  if (_node != NULL)
  {
    _node = _node->_next;

    if (_node == NULL) 
    {
      unsigned long last = [_table size] - 1;

      if (_index < last)
      {
        do
        {
          _index++;

          _node = getNode(_table, _index);
        }
        while ((_node == NULL) && (_index < last));
      }
    }
  }

  return (_node != NULL) ? _node->_object : nil;
}

//
// Get the previous object in the table
//
// @return the previous object (or nil)
//

- (id) prev
{
  if (_node != NULL)
  {
    _node = _node->_prev;

    if ((_node == NULL) && (_index > 0))
    {
      do
      {
        _index--;

        _node = getNode(_table, _index);
      }
      while ((_node == NULL) && (_index > 0));

      if (_node != NULL)
      {
        while (_node->_next != NULL)
        {
          _node = _node->_next;
        }
      }
    }
  }

  return (_node != NULL) ? _node->_object : nil;
}

//
// Get the last object in the table
//
// @return the last object (or nil)
//

- (id) last
{
  _node = NULL;

  if (_table != nil)
  {
    _index = [_table size];

    do
    {
      _index--;

      _node = getNode(_table, _index);
    }
    while ((_node == NULL) && (_index > 0));

    if (_node != NULL)
    {
      while (_node->_next != NULL)
      {
        _node = _node->_next;
      }
    }
  }
  else
    WARNING(DW_OBJECT_NOT_INIT, "hashTable");

  return (_node != NULL) ? _node->_object : nil;
}

//
// Set the current object to another object
//
// @param object   the object to be stored in current node
//
// @return the previous stored object (or nil)
//

- (id) object :(id) object
{
  if (_node != NULL)
  {
    _node->_object = object;
  }
  
  return (_node != NULL) ? _node->_object : nil;
}

//
// Get the current object
//
// @return the current object (or nil)
//

- (id) object
{
  return (_node != NULL) ? _node->_object : nil;
}

//
// Get the key of the current object
//
// @return a referencee to the key of the current object (or nil)
//

- (id) key
{
  return (_node != NULL) ? _node->_key : nil;
}

@end

/*==========================================================================*/
